//https://leetcode.cn/problems/maximize-win-from-two-segments/?envType=daily-question&envId=2024-09-11

class Solution {
public:
    int maximizeWin(vector<int>& prizePositions, int k) {
        int n = prizePositions.size(), left = 0, right = 0, ans = 0;
        if((2 * k + 1) >= (prizePositions[n - 1] - prizePositions[0])) return n;
        vector<int> dp(n + 1);
        while(right < n)
        {
            while (prizePositions[right] - prizePositions[left] > k) {
                left++;
            }
            ans = max(ans, dp[left] + right - left + 1);
            dp[right + 1] = max(dp[right], right - left + 1);
            right++;
        }
        return ans;
    }
};